`
https://leetcode.cn/problems/all-elements-in-two-binary-search-trees/
`

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {number[]}
 */
var getAllElements = function (root1, root2) {
  // BST 有序迭代器
  const t1 = new BSTIterator(root1);
  const t2 = new BSTIterator(root2);
  const res = [];
  // 类似合并有序链表的算法逻辑
  while (t1.hasNext() && t2.hasNext()) {
    if (t1.peek() > t2.peek()) {
      res.push(t2.next());
    } else {
      res.push(t1.next());
    }
  }
  // 如果有一棵 BST 还剩元素，添加到最后
  while (t1.hasNext()) {
    res.push(t1.next());
  }
  while (t2.hasNext()) {
    res.push(t2.next());
  }
  return res;
};

// https://leetcode.cn/problems/binary-search-tree-iterator/
// BST 有序迭代器
class BSTIterator {

  constructor(root) {
    this.stk = [];
    this.pushLeftBranch(root);
  }

  pushLeftBranch(p) {
    // 左侧树枝一撸到底
    while (p !== null) {
      this.stk.push(p);
      p = p.left;
    }
  }

  peek() {
    return this.stk[this.stk.length - 1].val;
  }

  next() {
    let p = this.stk.pop();
    this.pushLeftBranch(p.right);
    return p.val;
  }

  hasNext() {
    return this.stk.length > 0;
  }
}